package com.note.feng.leetcode.algorithms.easy.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TwoHundredFiftySeven {

    /**
     * 257 二叉树的所有路径
     * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
     *
     * 叶子节点 是指没有子节点的节点。
     *  
     * 示例 1：
     *
     * 输入：root = [1,2,3,null,5]
     * 输出：["1->2->5","1->3"]
     * 示例 2：
     *
     * 输入：root = [1]
     * 输出：["1"]
     *
     * 提示：
     *
     * 树中节点的数目在范围 [1, 100] 内
     * -100 <= Node.val <= 100
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/binary-tree-paths
     */
    /**
     *解法：深度优先
     * 在遍历二叉树时，有两种情况：
     * 1.当前节点不是叶子节点，则在当前路径的末尾添加该节点，并继续遍历该节点的每一个子节点
     * 2.当前节点是叶子节点，则在当前路径的末尾添加该节点，我们就得到了一条从根节点到叶子节点的路径
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        getPath(root, "", list);
        return list;
    }
    private void getPath(TreeNode node, String path, List<String> list){
        if(node == null){
            return;
        }
        StringBuffer sb = new StringBuffer(path);
        sb.append(String.valueOf(node.val));
        if(node.left == null && node.right == null){
            list.add(sb.toString());
        }else{
            sb.append("->");
            getPath(node.left, sb.toString(), list);
            getPath(node.right, sb.toString(), list);
        }
    }

    /**
     * 解法二：广度优先
     * 维护两个队列，一个队列存储还有子节点的节点，一个队列存储根节点到当前节点的路径，
     * 1.当前节点不是叶子节点，则在当前路径的末尾添加该节点，将其子节点和当前路径分别加入队列
     * 2.当前节点是叶子节点，则在当前路径的末尾添加该节点，我们就得到了一条从根节点到叶子节点的路径
     * @param root
     * @return
     */
    public List<String> binaryTreePaths2(TreeNode root) {
        List<String> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<String> pathQueue = new LinkedList<>();
        nodeQueue.offer(root);
        pathQueue.offer(String.valueOf(root.val));
        while (!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.poll();
            String path = pathQueue.poll();
            if(node.left == null && node.right == null){
                list.add(path);
            }else {
                if(node.left != null){
                    nodeQueue.offer(node.left);
                    pathQueue.offer(path + "->" + node.left.val);
                }
                if(node.right != null){
                    nodeQueue.offer(node.right);
                    pathQueue.offer(path + "->" + node.right.val);
                }
            }
        }
        return list;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
